package com.tree.sort;

import cn.hutool.json.JSONUtil;
import com.alibaba.fastjson.JSON;

/**
 * @ClassName com.tree.sort
 * Description: <类功能描述>. <br>
 * <p>
 * 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
 * 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
 * 快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
 * 快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
 * 快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
 * 1. 算法步骤
 * 从数列中挑出一个元素，称为 "基准"（pivot）;
 * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
 * </p>
 * @Author tree
 * @Date 2019-12-11 00:24
 * @Version 1.0
 */
public class QuickSort {

    public static void main(String[] args) {
        sort();
    }


    public static int[] sort() {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = {3,1,6,0,2,7};

        int[] res =  quickSort(arr, 0, arr.length - 1);
        System.out.println(JSONUtil.toJsonStr(res));
        return  res;
    }

    private static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition3(arr, left, right);
            System.out.println("开始左部，partitionIndex="+partitionIndex);
            quickSort(arr, left, partitionIndex - 1);
            System.out.println("开始右部，partitionIndex="+partitionIndex);
            quickSort(arr, partitionIndex + 1, right);

        }

        return arr;
    }

    private static int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        System.out.println((index-1)+","+JSON.toJSONString(arr));
        return index - 1;
    }


    private static int partition2(int[] arr, int left, int right) {
        // 选择最右边的元素作为基准值
        int pivot = arr[right];
        // 初始化指向小于等于基准值的元素的索引
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                // 将比基准值小或相等的元素交换到前面
                swap(arr, ++i, j);
            }
        }
        // 将基准值放入正确的位置
        swap(arr, i + 1, right);

        // 返回基准值所在的索引
        return i + 1;
    }

    /**
     * 双边指针（挖坑法） {3,5,4,2,6,7,1,5,6};
     * 思路：
     * 创建左右指针。
     * 记录左指针数据为分界值 pivot，
     * 此时左指针视为"坑"，里面的数据可以被覆盖。
     *
     * 首先从右向左找出比pivot小的数据，
     * 找到后立即放入左边坑中，当前位置变为新的"坑"，
     * 然后从左向右找出比pivot大的数据，
     * 找到后立即放入右边坑中，当前位置变为新的"坑"，
     *
     * 结束循环后将最开始存储的分界值放入当前的"坑"中，
     * 返回当前"坑"下标（即分界值下标）
     */
    public static int partition3(int[] array,int left,int right) {
        int pivot = array[left];
        int hole = left;
        while (left < right) {
            // 从右向左找出比pivot小的数据，
            while (left < right && array[right] >= pivot) {
                right--;
            }
            // 找到后立即放入左边坑中，当前位置变为新的"坑"
            //找到小于key的值就填坑
            array[hole] = array[right];
            //形成新的坑
            hole = right;
            // 从左向右找出比pivot大的数据
            while (left < right && array[left] <= pivot) {
                left++;
            }
            // 找到后立即放入右边坑中，当前位置变为新的"坑"
            array[hole] = array[left];
            hole = left;
            System.out.println("===left="+left+";right = "+right+"; arr="+JSONUtil.toJsonStr(array));
        }
        // 将最开始存储的分界值放入当前的"坑"中
        array[hole] = pivot;
//        System.out.println("right="+right+";tmp="+pivot
//                +"\nleft="+left+";array["+left+"]="+array[left]
//                +"\n;right="+right+";array["+right+"]="+array[right]
//                +"\n;array="+JSONUtil.toJsonStr(array));
        return hole;

    }

    public static int partition4(int[] array,int left,int right) {
        int pivot = array[left];
        int i = left+1;
        int j = right;
        while (i < j) {
            // 从右向左找出比pivot小的数据，
            while (i < j && array[j] >= pivot) {
                j--;
            }
            // 从左向右找出比pivot大的数据
            while (i < j && array[i] <= pivot) {
                i++;
            }
            swap(array,i,j);
            System.out.println("===left="+left+";right = "+right+"; arr="+JSONUtil.toJsonStr(array));
        }
        // 将最开始存储的分界值放入当前的"坑"中
        array[left] = array[i];
        array[j] = pivot;
//        System.out.println("right="+right+";tmp="+pivot
//                +"\nleft="+left+";array["+left+"]="+array[left]
//                +"\n;right="+right+";array["+right+"]="+array[right]
//                +"\n;array="+JSONUtil.toJsonStr(array));
        return j;

    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }



    /**
     * 入口函数（递归方法），算法的调用从这里开始。
     */
    public void quickSort2(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }

        // 核心算法部分：分别介绍 双边指针（交换法），双边指针（挖坑法），单边指针
        int pivotIndex = doublePointerSwap(arr, startIndex, endIndex);
        // int pivotIndex = doublePointerHole(arr, startIndex, endIndex);
        // int pivotIndex = singlePointer(arr, startIndex, endIndex);

        // 用分界值下标区分出左右区间，进行递归调用
        quickSort2(arr, startIndex, pivotIndex - 1);
        quickSort2(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 双边指针（交换法）
     * 思路：
     * 记录分界值 pivot，创建左右指针（记录下标）。
     * （分界值选择方式有：首元素，随机选取，三数取中法）
     *
     * 首先从右向左找出比pivot小的数据，
     * 然后从左向右找出比pivot大的数据，
     * 左右指针数据交换，进入下次循环。
     *
     * 结束循环后将当前指针数据与分界值互换，
     * 返回当前指针下标（即分界值下标）
     */
    private int doublePointerSwap(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int leftPoint = startIndex;
        int rightPoint = endIndex;

        while (leftPoint < rightPoint) {
            // 从右向左找出比pivot小的数据
            while (leftPoint < rightPoint
                    && arr[rightPoint] > pivot) {
                rightPoint--;
            }
            // 从左向右找出比pivot大的数据
            while (leftPoint < rightPoint
                    && arr[leftPoint] <= pivot) {
                leftPoint++;
            }
            // 没有过界则交换
            if (leftPoint < rightPoint) {
                int temp = arr[leftPoint];
                arr[leftPoint] = arr[rightPoint];
                arr[rightPoint] = temp;
            }
        }
        // 最终将分界值与当前指针数据交换
        arr[startIndex] = arr[rightPoint];
        arr[rightPoint] = pivot;
        // 返回分界值所在下标
        return rightPoint;
    }

    /**
     * 双边指针（挖坑法）
     * 思路：
     * 创建左右指针。
     * 记录左指针数据为分界值 pivot，
     * 此时左指针视为"坑"，里面的数据可以被覆盖。
     *
     * 首先从右向左找出比pivot小的数据，
     * 找到后立即放入左边坑中，当前位置变为新的"坑"，
     * 然后从左向右找出比pivot大的数据，
     * 找到后立即放入右边坑中，当前位置变为新的"坑"，
     *
     * 结束循环后将最开始存储的分界值放入当前的"坑"中，
     * 返回当前"坑"下标（即分界值下标）
     */
    private int doublePointerHole(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int leftPoint = startIndex;
        int rightPoint = endIndex;

        while (leftPoint < rightPoint) {
            // 从右向左找出比pivot小的数据，
            while (leftPoint < rightPoint
                    && arr[rightPoint] > pivot) {
                rightPoint--;
            }
            // 找到后立即放入左边坑中，当前位置变为新的"坑"
            if (leftPoint < rightPoint) {
                arr[leftPoint] = arr[rightPoint];
                leftPoint++;
            }
            // 从左向右找出比pivot大的数据
            while (leftPoint < rightPoint
                    && arr[leftPoint] <= pivot) {
                leftPoint++;
            }
            // 找到后立即放入右边坑中，当前位置变为新的"坑"
            if (leftPoint < rightPoint) {
                arr[rightPoint] = arr[leftPoint];
                rightPoint--;
            }
        }
        // 将最开始存储的分界值放入当前的"坑"中
        arr[rightPoint] = pivot;
        return rightPoint;
    }

    /**
     * 单边指针
     * 思路：
     * 记录首元素为分界值 pivot, 创建标记 mark 指针。
     * 循环遍历与分界值对比。
     * 比分界值小，则 mark++ 后与之互换。
     * 结束循环后，将首元素分界值与当前mark互换。
     * 返回 mark 下标为分界值下标。
     */
    private int singlePointer(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int markPoint = startIndex;

        for (int i = startIndex + 1; i <= endIndex; i++) {
            // 如果比分界值小，则 mark++ 后互换。
            if (arr[i] < pivot) {
                markPoint++;
                int temp = arr[markPoint];
                arr[markPoint] = arr[i];
                arr[i] = temp;
            }
        }
        // 将首元素分界值与当前mark互换
        arr[startIndex] = arr[markPoint];
        arr[markPoint] = pivot;
        return markPoint;
    }

}

